\chapter{Подсчет числа отображений}

Лекция от 22 сентября 2011 года.

\subsection{Название столь длинное, что не помещается}

Начнем с простого, что такое отображение:

\begin{Def}
$f : X \rightarrow Y$, $\left|X\right|=n$, $\left|Y\right|=k$, причем $\forall x \in X \exists ! y \in Y [y = f\left(x\right)]$
\end{Def}

какие же они бывают:

\begin{Def}
Отображение $f$ инъективно, если $\forall x,z \in X [f\left(x\right)=f\left(z\right) \Rightarrow x=z]$
\end{Def}

\begin{Def}
Отображение $f$ сюрективно, если $\forall y \in Y \exists x \in X [f\left(x\right)=y]$
\end{Def}

\begin{Def}
Отображение $f$ биективно, если $\forall y \in Y \exists x \in X [f\left(x\right)=y]$
\end{Def}

Найти число всех возможных сюректиных отображений для заданных мощностей множеств и есть задача этой части лекции.

\begin{Def}
$\hat S \left(n,k\right)$ - числа Моргана, количество сбрективных отображений из множества мощностью $n$ в множество мощностью $k$, причем $n \ge k$.
\end{Def}

Чтобы посчитать число сюрективных отображений, посчитаем сначала число всех возможных отображений, оно, очевидно равно $k^n$. Любое отображение $f$ можно рассматривать как сюрективное отображение на $Im f$.

$\left|Im f\right| \le \left|X\right| = n$. Разобьем все отображения на $n$ блоков, таким образом, чтобы в блок $B_i$-ый попадали отображения для, которых $\left|Im f\right|=i$, тогда справделива формула:
\[
	\left| B_i \right| = \binom{k}{i} \hat S \left(n,i\right)
\]
Тогда:
\[
	k^n = \sum_{i=1}^n \binom{k}{i} \hat S \left(n,i\right) = \sum_{i=0}^k \binom{k}{i} \hat S \left(n,i\right)
\]

\paragraph{Примечание: } $\hat S \left(n,0\right) = \hat S \left(n,i\right) = 0$, $\forall i > n$

Теперь необходимо произвести "обращение" формулы, чтобы вывести формулу числа Моргана, но пока мы этого делать не умеем, поэтому забегая немного вперед приведем формулу обращения для двух заимосвязанных последоательностей:
\begin{equation}
	\begin{split}
	& f = \left(f_0, f_1, f_2, f_3, ...\right) \\
	& g = \left(g_0, g_1, g_2, g_3, ...\right) \\
	& f_k = \sum_{i=0}^k \binom{k}{i} g_i \Leftrightarrow g_k = \sum_{i=0}^k {\left(-1\right)}^{k-i}\binom{k}{i} f_i
	\end{split}
	\label{math::invert}
\end{equation}

Теперь, пользуясь упавшей нам на голову формулой обращения получим выражения для чисел Моргана:
\begin{equation}
\hat S \left(n,k\right) = \sum_{i=0}^k {\left(-1\right)}^{k-i} \binom{k}{i} i^n
\end{equation}

Теперь через симметрию биномиальных коэффициентов получим новый вид:
\begin{equation}
\hat S \left(n,k\right) = \sum_{i=0}^k {\left(-1\right)}^i\binom{k}{i} {\left(k-i\right)}^n
\end{equation}

\subsection{Не менее длинное название}

Любое отображение $f$ из можества $X$ на множество $Y$ можно воспринимать как $k$-разделение множества $X$ и таких разделений будет $k^n$. Зафиксируем теперь $k$ неотрицательных чисел $a_i$, причем $\sum_i a_i = n$ и посчитаем число всех возможных таких векторов, т. е. количество целочисленных решений уравнения $\sum_i a_i = n$. Количество таких решений: $\left(\binom{k}{n}\right)$.

Каждое такое решение является спецификацией множества разделений, количество разделений соответствующих этой спецификации:
\[
	\binom{n}{a_1}\binom{n-a_1}{a_2}\binom{n-a_1-a_2}{a_3}...\binom{n-a_1-a_2-a_3-...-a_{k-1}}{a_k} = \frac{n!}{a_1!a_2!a_3!...a_k!}
\]

Теперь вспомним, а что же такое мы считали? А посчитали мы в конечном итоге число всех разделений равно $k^n$, а следовательно:
\begin{equation}
\sum_{\substack{a_i \ge 0 \\ a_1+a_2+...+a_k=n}} \frac{n!}{a_1!a_2!...a_k!} = k^n
\end{equation}

Изменив нестрогое неравнество в знаке суммы на строгое получим только сюрективные отображения:
\begin{equation}
\sum_{\substack{a_i > 0 \\ a_1+a_2+...a_k=n}} \frac{n!}{a_1!a_2!...a_k!} = \hat S \left(n,k\right)
\end{equation}

Ну и наконец последня фишка, если нам не важен порядок элементов, т. е. нужно разбиение, а не разделение, то формула преобразуется:
\begin{equation}
S\left(n,k\right) = \frac{\hat S \left(n,k\right)}{k!}
\end{equation}
или
\begin{equation}
S\left(n,k\right) = \frac{1}{k!} \sum_{\substack{a_i > 0 \\ a_1 + a_2 + .. + a_k = n}} \frac{n!}{a_1!a_2!...a_k!}
\end{equation}
\begin{equation}
S\left(n,k\right) = \frac{1}{k!} \sum_{i=0}^k {\left(-1\right)}^i \binom{k}{i} {\left(k-i\right)}^n
\end{equation}
А для людей знающих (помнящих на самом деле), это числа Стирлинга второго рода, вот так вот!
